The present invention relates to data processing techniques for use in communications systems and the like, and more particularly to the optimization of binary tree search structures used in such systems.
Determination of a minimum or maximum value in a set of data is a common operation which is often accomplished using specialized hardware. As an example, many communications systems utilize the Viterbi algorithm, which requires a determination of the most probable path for each state. This must be estimated by finding the path having the maximum metric (if correlation metric is used) or minimum metric (if Euclidean distance is used) among other concurrent paths. An efficient means for determination of the maximum or minimum metric is required.
A method for finding the minimum in an array of N values which is storage efficient is to store the running estimate of the minimum and its location and compare it to each of the (N−1) other values in the array. This method requires (N−1) comparisons which will take at least (N−1) clock cycles.
For delay sensitive systems or for systems having fewer than (N−1) clock cycles to do the comparisons, a standard alternate approach is the binary tree search structure. In a binary tree search structure, each layer contains half as many comparators and storage elements as the previous layer, thus reducing the latency to log2N clock cycles and allowing for pipelining. The downside of such a structure is the addition of (N−1) comparators and storage elements.
For the foregoing reasons, there is a need for a method and apparatus which limits the latency inherent in systems using a running estimate and which reduces the number of storage elements used in a standard binary tree search structure.